/**
 * 层级树工具类
 * @author lms 2021.03.31
 */
package ms.core.tool;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class TreeTool {

	//方法一：递归构建json树，返回的roots即为结果
    public static void buildTree(String parentId, List<TreeNode> list, List<TreeNode> roots){
        for(TreeNode node: list){
            if(StrTool.equals(parentId, node.getPid(), true)){
                roots.add(node);
                buildTree(node.getId(), list, node.getChilds());
            }
        }
    }

    private static Map<String,TreeNode> listToTreeMap(List<TreeNode> list, String root){
        //list 转 map
    	Map<String, TreeNode> map = new LinkedHashMap<String, TreeNode>();
        for(TreeNode node: list) {
            map.put(node.getId(), node);
        }

        Iterator<TreeNode> iter = map.values().iterator();
        while(iter.hasNext()){
        	TreeNode node = iter.next();
            if(node.getPid()==root) continue;

            TreeNode parentNode = map.get(node.getPid());
            if(parentNode != null){
                parentNode.getChilds().add(node);
            }
        }
 
        return map;
    }

	//方法二：借助Map完成
   public static List<TreeNode> buildTree(List<TreeNode> list, String root){
        if(list.size()<=0) return null;

        Map<String, TreeNode> map = listToTreeMap(list, root);
        if(map.size() == 0) return null;

        List<TreeNode> roots = new ArrayList<TreeNode>();
        Iterator<TreeNode> iter = map.values().iterator();

        while(iter.hasNext()){
        	TreeNode treeNode = iter.next();
            if(StrTool.equals(root, treeNode.getPid(), true)){
                roots.add(treeNode); 
            }
        }
        return roots;
    }

   /**
    * 按树深度遍历[递归]算法查找节点
    * @param root
    * @param id
    */
   public static TreeNode deepSearchTreeNode(TreeNode root, String id) {
	   if (root!=null) {
		   if (StrTool.equals(id, root.getId(), true))
			   return root;

		   List<TreeNode> childs = root.getChilds();
		   if (childs!=null) {
			   for(int i=0; i<childs.size(); i++) {
				   TreeNode node = deepSearchTreeNode(childs.get(i), id);
				   if (node!=null) return node;
			   }
		   }
	   }
	   return null;
   }

   /**
    * 按树广度遍历[非递归]算法查找节点
    * @param root
    * @param id
    */
   public static TreeNode spanSearchTreeNode(TreeNode root, String id) {
	   if (root==null) return null;

	   //借助队列先进先出特性
	   Queue<TreeNode> queue=new LinkedList<TreeNode>();
	   queue.offer(root);
	   
	   while(!queue.isEmpty()) {
		   TreeNode node = queue.poll();
		   if (StrTool.equals(id, node.getId(), true)) 
			   return node;
		   
		   List<TreeNode> childs = node.getChilds();
		   if (childs!=null) {
			   for (int i=0; i<childs.size(); i++) queue.offer(childs.get(i));
		   }
	   }

	   return null;
   }

	/**
	 * 按树广度遍历[非递归]算法遍历所有节点
	 * @param root
	 * @param id
	*/
	public static List<TreeNode> iteratorTree(TreeNode root) {
		List<TreeNode> rets = new ArrayList<>();
		if (root==null) return rets;

		//借助队列先进先出特性
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		queue.offer(root);

		while(!queue.isEmpty()) {
			TreeNode node = queue.poll();
			rets.add(node);
			List<TreeNode> childs = node.getChilds();
			if (childs!=null) {
				for (int i=0; i<childs.size(); i++) queue.offer(childs.get(i));
			}
		}

		return rets;
	}

	//节点实体
	public static class TreeNode {
		private String id;						//节点id
		private String pid;						//父节点id
		private Object data;					//节点数据
		private List<TreeNode> childs=null;		//子节点

		public TreeNode(String id, String pid, Object data, List<TreeNode> childs){ 
			this.id = id;
			this.pid = pid;
			this.data = data;
			this.childs = childs;
		}

		public String getId() { return id; }
		public void setId(String id) { this.id = id; }
		
		public String getPid() { return pid; }
		public void setPid(String pid) { this.pid = pid; }
		
		public Object getData() { return data; }
		public void setData(Object data) { this.data = data; }
		
		public List<TreeNode> getChilds() { 
			if (childs==null) childs = new ArrayList<TreeNode>();
			return childs; 
		}
		public void setChilds(List<TreeNode> childs) { this.childs = childs; }
	}
}
